class Solution:
    """
    128. 最长连续序列
    https://leetcode-cn.com/problems/longest-consecutive-sequence/
    @date 2021年1月15日20:22:43
    @author mizzle rain
    """

    def longestConsecutive(self, nums):
        """
        空间换时间，可以将复杂度降为O(n)
        """
        n = len(nums)
        if n == 0:
            return 0
        res = 0
        tr_left, tr_right = dict(), dict()
        for num in nums:
            left, right = tr_right.get(num-1, 0), tr_left.get(num+1, 0)
            tr_left[num-left] = max(tr_left.get(num-left,0), left + right + 1) 
            tr_right[num+right] = max(tr_right.get(num+right,0), left + right + 1) 
            res = max(res, left + right + 1)
        return res


if __name__ == "__main__":
    s = Solution()
    res = s.longestConsecutive([1, 2, 0, 1])
    print(res)
